//#include <iostream>
//#include <vector>
//#include <climits>
//using namespace std;
//int Find(vector<int>& cost, vector<bool>& visited, int N) {
//    int minCost = INT_MAX;
//    int minCostVertex = -1;
//    for (int i = 0; i < N; i++) {
//        if (!visited[i] && cost[i] < minCost) {
//            minCost = cost[i];
//            minCostVertex = i;
//        }
//    }
//    return minCostVertex;
//}
//void Algorithm(vector<vector<int>>& graph, int N) {
//    vector<int> cost(N, INT_MAX);
//    vector<bool> visited(N, false);
//    vector<int> parent(N, -1);
//    cost[0] = 0;
//    for (int i = 0; i < N - 1; i++) {
//        int u = Find(cost, visited, N);
//        visited[u] = true;
//        for (int v = 0; v < N; v++) {
//            if (graph[u][v] && !visited[v] && graph[u][v] < cost[v]) {
//                cost[v] = graph[u][v];
//                parent[v] = u;
//            }
//        }
//    }
//    for (int i = 1; i < N; i++) {
//        cout << parent[i] + 1 << "," << i + 1 << "," << graph[parent[i]][i] << endl;
//    }
//}
//int main() {
//    int N, M;
//    cin >> N >> M;
//    vector<vector<int>> graph(N, vector<int>(N, 0));
//    for (int i = 0; i < M; i++) {
//        int u, v, cost;
//        cin >> u >> v >> cost;
//        graph[u - 1][v - 1] = cost;
//        graph[v - 1][u - 1] = cost;
//    }
//    Algorithm(graph, N);
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//vector<int>fa(1000, 5);
//struct DATA
//{
//    int x = 0, y = 0;
//}p[5000];
//int Find(int x)
//{
//    if (fa[x] == x)
//        return x;
//    return fa[x] = Find(fa[x]);
//}
//void Union(int x, int y)
//{
//    int a = Find(x);
//    int b = Find(y);
//    if (a == b)
//        return;
//    fa[a] = b;
//}
//int main()
//{
//    int n = 0, m = 0, K = 0;
//    vector<int> vis(1000, 0);
//    cin >> n >> m;
//    for (int i = 0; i < n; i++)
//    {
//        fa[i] = i;
//    }
//    for (int i = 0; i < m; i++)
//    {
//        cin >> p[i].x >> p[i].y;
//        Union(p[i].x, p[i].y);
//    }
//    int num = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (fa[i] == i) num++;
//    }
//    cin >> K;
//    int cnt = K;
//    while (K--)
//    {
//        int x;
//        cin >> x;
//        vis[x] = 1;
//        int num1 = 0;
//        for (int i = 0; i < n; i++) fa[i] = i;
//        for (int i = 0; i < m; i++)
//        {
//            if (vis[p[i].x] == 1 || vis[p[i].y] == 1)
//            {
//                continue;
//            }
//            Union(p[i].x, p[i].y);
//        }
//        for (int i = 0; i < n; i++)
//        {
//            if (fa[i] == i)
//            {
//                num1++;
//            }
//        }
//        if (num1 == num || num1 == num + 1)
//        {
//            cout << "City " << x << " is lost." << endl;
//        }
//        else
//        {
//            cout << "Red Alert: City " << x << " is lost!" << endl;
//        }
//        num = num1;
//    }
//    if (cnt == n)
//    {
//        cout << "Game Over." << endl;
//    }
//    return 0;
//}